package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname IsSymmetric_0101
 * @Author happytaohaha
 * @Date 2020/3/12
 * @Description 对称二叉树  O(n)
 */
public class IsSymmetric_0101 {

    /**
     * 递归
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return mirror(root,root);
    }

    private boolean mirror(TreeNode root, TreeNode root1) {
        if(root ==null && root1==null) {
            return true;
        }
        if(root == null || root1 == null){
            return false;
        }
        return (root.val==root1.val)&& mirror(root.left,root1.right) && mirror(root.right,root1.left);
    }


    /**
     * 迭代
     *
     * 除了递归的方法外，我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。最初，队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS，但存在一些关键差异。每次提取两个结点并比较它们的值。然后，将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null) {continue;}
            if (t1 == null || t2 == null) {return false;}
            if (t1.val != t2.val) {return false;}
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }

}
